﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
using namespace std;


//在字符串中找出连续最⻓的数字串
//https://www.nowcoder.com/practice/bd891093881d4ddf9e56e7cc8416562d?tpId=182&tqId=34785&ru=/exam/oj

//int main()
//{
//	string s, tmp, ret;
//	cin >> s;
//	
//	int flag = 0;
//	for (auto ch : s)
//	{
//		if (isdigit(ch) && flag == 0)
//		{
//			tmp.clear();
//			flag = 1;
//			tmp += ch;
//		}
//		else if (isdigit(ch) && flag == 1)
//		{
//			tmp += ch;
//		}
//		else if (!isdigit(ch) && flag == 1)
//		{
//			if (tmp.size() > ret.size())
//				ret = tmp;
//			flag = 0;
//		}
//	}
//	if (tmp.size() > ret.size())
//		ret = tmp;
//	
//	cout<<ret;
//
//	return 0;
//}


//岛屿数量
//https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e?tpId=196&tqId=37167&ru=/exam/oj
//BFS/DFS


//class Solution {
//public:
//    int solve(vector<vector<char>>& grid) 
//    {
//        m = grid.size(), n = grid[0].size();
//        int num = 0;
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == '1' && vis[i][j] == 0)
//                {
//                    bfs(i, j, grid);
//                    num++;
//                }
//            }
//        }
//        return num;
//    }
//private:
//    void bfs(int x, int y, vector<vector<char>>& grid)
//    {
//        queue<pair<int, int>>q;
//        q.push({ x, y });
//        vis[x][y] = 1;
//        while (q.size())
//        {
//            int x = q.front().first, y = q.front().second;
//            q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int nx = x + dx[i];
//                int ny = y + dy[i];
//
//                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[x][y] == '1'
//                    && vis[nx][ny] == 0)
//                {
//                    q.push({ nx,ny });
//                    vis[nx][ny] = 1;
//                }
//            }
//        }
//    }
//
//    int m, n;
//    int vis[205][205] = { 0 };
//    int dx[4] = { 1,0,-1,0 };
//    int dy[4] = { 0,1,0,-1 };
//};


//拼三角
//https://ac.nowcoder.com/acm/problem/219046
//枚举

//class Solution
//{
//public:
//	void solve()
//	{
//		int n;
//		cin >> n;
//		while (n--)
//		{
//			path.clear();
//			memset(vis, 0, sizeof(vis));
//
//			for (int i = 0; i < 6; i++)
//			{
//				cin >> arr[i];
//			}
//
//			if (dfs(0))
//				cout << "Yes" << endl;
//			else
//				cout << "No" << endl;
//		}
//	}
//private:
//	bool dfs(int index)
//	{
//		if (index == 3)
//		{
//			if (isTangle())
//				return true;
//			return false;
//		}
//
//		for (int i = 0; i < 6; i++)
//		{
//			if (vis[i] == 0)
//			{
//				path.push_back(i);
//				vis[i] = 1;
//				if (dfs(index + 1))
//					return true;
//				path.pop_back();
//				vis[i] = 0;
//			}
//		}
//		return false;
//	}
//
//	bool isTangle()
//	{
//		vector<int> path1 = path;
//		vector<int> path2;
//		for(int i=0;i<6;i++)
//		{
//			int flag = 1;
//			for (auto num : path1)
//			{
//				if (num == i)
//				{
//					flag = 0;
//					break;
//				}
//			}
//			if (flag)
//				path2.push_back(i);
//		}
//		for (int i=0;i<3;i++)
//		{
//			path1[i] = arr[path1[i]];
//			path2[i] = arr[path2[i]];
//		}
//		sort(path1.begin(), path1.end());
//		sort(path2.begin(), path2.end());
//
//		if (path1[0] + path1[1] > path1[2] && path2[0] + path2[1] > path2[2])
//			return true;
//
//		return false;
//	}
//
//	vector<int> path;
//	int arr[6];
//	int vis[6] = { 0 };
//};
//
//int main()
//{
//	Solution s;
//	s.solve();
//
//	return 0;
//}
